# 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 
# 
#  
# 
#  示例 1： 
#  
#  
# 输入：head = [1,2,3,4,5], n = 2
# 输出：[1,2,3,5]
#  
# 
#  示例 2： 
# 
#  
# 输入：head = [1], n = 1
# 输出：[]
#  
# 
#  示例 3： 
# 
#  
# 输入：head = [1,2], n = 1
# 输出：[1]
#  
# 
#  
# 
#  提示： 
# 
#  
#  链表中结点的数目为 sz 
#  1 <= sz <= 30 
#  0 <= Node.val <= 100 
#  1 <= n <= sz 
#  
# 
#  
# 
#  进阶：你能尝试使用一趟扫描实现吗？ 
# 
#  Related Topics 链表 双指针 👍 2997 👎 0
from typing import Optional

from LeetCode.Test.LinkTool import LinkedListTool, ListNode


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.


class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # 虚构一个头节点
        home = ListNode(0, head)
        size = 0
        cur = home
        while cur.next:
            size += 1
            cur = cur.next
        # 倒数第n个就是正数 总个数-n 个，需要定位到它前一个故是size-n-1,但是索引是从0开始的，故是size-n
        cur = home
        for _ in range(size - n):
            cur = cur.next
        cur.next = cur.next.next
        return home.next


# leetcode submit region end(Prohibit modification and deletion)
LinkedListTool.each(Solution().removeNthFromEnd(LinkedListTool([1, 2, 3, 4, 5]), n=2))
